/*
  LeetCode -> https://leetcode.com/problems/longest-palindromic-subsequence/

  Given a string s, find the longest palindromic subsequence's length in s.
  You may assume that the maximum length of s is 1000.

*/

const longestPalindromeSubsequence = s => {
  const n = s.length

  const dp = new Array( n ).fill( 0 ).map( item => new Array( n ).fill( 0 ).map( item => 0 ) )

  // fill predefined for single character
  for ( let i = 0; i < n; i++ ) {
    dp[ i ][ i ] = 1
  }

  for ( let i = 1; i < n; i++ ) {
    for ( let j = 0; j < n - i; j++ ) {
      const col = j + i
      if ( s[ j ] === s[ col ] ) {
        dp[ j ][ col ] = 2 + dp[ j + 1 ][ col - 1 ]
      } else {
        dp[ j ][ col ] = Math.max( dp[ j ][ col - 1 ], dp[ j + 1 ][ col ] )
      }
    }
  }

  return dp[ 0 ][ n - 1 ]
}

const main = () => {
  console.log( longestPalindromeSubsequence( 'bbbab' ) ) // 4
  console.log( longestPalindromeSubsequence( 'axbya' ) ) // 3
  console.log( longestPalindromeSubsequence( 'racexyzcxar' ) ) // 7
}

main()
